Algorithms and decision rules are often deployed in settings where the individuals they affect respond to them, or where behavior depends on beliefs, incentives, and constraints. In this talk, I will discuss two theoretical models that study how such responses shape outcomes.
First, I will consider strategic classification, where agents manipulate their features, at a cost, to receive a positive classification from a learner’s classifier. We study learning objectives with minimax group fairness guarantees in a population consisting of several groups, where each group may have its own cost function. For separable costs and a small number of groups, we give an efficient algorithm for learning an approximately optimal deterministic classifier. For general cost functions, we give oracle-efficient algorithms for learning approximately optimal randomized classifiers when the hypothesis class has finite strategic VC dimension.
I will then turn to a different setting: decision-making between stable and risky choices when the risky option may improve over time. Motivated by work in philosophy and sociology on grit, we develop a quantitative model using improving multi-armed bandits and study how an individual’s level of grittiness affects both the strategy they follow and the reward they accrue. We consider two formal models of rationality—competitive ratio and Bayesian quantification of uncertainty—and study interventions including increasing grit and providing a financial safety net.
The two papers can be found on ArXiv at https://arxiv.org/abs/2410.02513 and https://arxiv.org/abs/2503.02952.